package algorithm;

/**
 * @Author pc
 * @Date 2019/8/20 14:12
 * @Description 排序（快排、堆排、归并）
 */
public class SortUtils {
    /**
     * 快排
     * @param num
     */
    public static void quickSort(int[] num){
        quickSort(num,0,num.length-1);
    }
    private static void quickSort(int[] num,int left,int right){
        if(left<right){
            int mid = num[left];
            int i = left;
            int j = right;
            while(i<j){
                while(i<j&&num[j]>mid)j--;
                num[i]=num[j];
                while(i<j&&num[i]<=mid)i++;
                num[j]=num[i];
            }
            num[i]=mid;
            quickSort(num,left,i-1);
            quickSort(num,i+1,right);
        }
    }

    /**
     * 归并排序
     * @param num
     */
    public static void mergeSort(int[] num){
        mergeSort(num,0,num.length-1);
    }
    private static void mergeSort(int[] num,int left,int right){
        if(left<right){
            int mid = (left+right)>>1;
            mergeSort(num,left,mid);
            mergeSort(num,mid+1,right);
            mergeSort(num,left,mid,right);
        }
    }
    private static void mergeSort(int[] num,int left,int mid,int right){
        int[] a = new int[mid-left+1];
        int[] b = new int[right-mid];
        int i = 0,k = left;
        for(i=0,k=left;i<a.length;i++,k++){
            a[i] = num[k];
        }
        for(i=0,k=mid+1;i<b.length;i++,k++){
            b[i] = num[k];
        }
        int[] tmp = mergeSort(a,b);
        System.arraycopy(tmp,0,num,left,right-left+1);
    }

    /**
     * 两个有序数组的归并
     * @param a
     * @param b
     * @return
     */
    public static int[] mergeSort(int[] a,int[] b){
        int[] res = new int[a.length+b.length];
        int i=0,j=0;
        int count = 0;
        while(i<a.length&&j<b.length){
            if(a[i]<b[j]){
                res[count++]=a[i];
                i++;
            }else{
                res[count++]=b[j];
                j++;
            }
        }
        while(i<a.length){
            res[count++]=a[i++];
        }
        while(j<b.length){
            res[count++]=b[j++];
        }
        return res;
    }

    /**
     * 堆排序
     * @param num
     */
    public static void heapSort(int[] num){
        int len = num.length;
        buildHeap(num,len);
        for(int i=0;i<num.length;i++){
            swap(num,0,--len);
            buildHeap(num,0,len);
        }
    }

    private static void buildHeap(int[] num,int size){
        for(int i=size/2;i>=0;i--){
            buildHeap(num,i,size);
        }
    }
    private static void buildHeap(int[] num,int cur,int size){
        int left = (cur<<1)+1;
        int right = (cur<<1)+2;
        int max = cur;
        if(left<size&&num[left]>num[max]){
            max = left;
        }
        if(right<size&&num[right]>num[max]){
            max = right;
        }
        if(max!=cur){
            swap(num,max,cur);
            buildHeap(num,max,size);
        }
    }
    private static void swap(int[] num,int i,int j){
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
}
